Embedding of Fibonacci Tree into Hyper-Star Network
AUTHORS
Jong-Seok Kim,North California Central University
Hyung Jae Chang,Troy University – Montgomery
Hyeong-Ok Lee,Suncheon National University
ABSTRACT
As the demand for high performance computing has been increased in these days, parallel processing system becomes widely used to improve the performance of computers. In parallel processing system, all processors are connected in an interconnection network where each processor has its own memory. Recently, Hyper-Star network HS(m,k) was proposed as a new interconnection network for parallel processing. HS(m,k) has the same characteristics as Hypercube and Star graph, and it is proven to have better network cost than Hypercube with the same number of nodes. Tree plays an important role as a data structure in parallel processing system and is a useful network structure to which a divide and conquer algorithm can be easily applied. When a new algorithm is designed, embedding a given network structure in another one is a good application where the new algorithm can be used. In this paper, we show how Fibonacci tree can be embedded in HS(2n,n) and analyze its result. In conclusion, the paper presents that the embedding is possible with the dilation 1.
KEYWORDS
Algorithm, Hyper-star network, Fibonacci tree, Embedding.
REFERENCES
[1] Y. Saad and M. H. Schultz, Topological properties of hypercubes. IEEE Transactions on Computers, Vol.37, No.7, pp.867-872 (1988)
[2] S. B. Akers, D. Harel, and B. Krishnamurthy, The Star graph: an attractive alternative to the N-cube, Proceedings of the International Conference on Parallel Processing, (1987) January 393-400.
[3] H.-O. Lee, J.-S. Kim, E. Oh, and H.-S. Lim, Hyper-star graph: a new interconnection network improving the network cost of the hypercube. Proceedings of the 1st EurAsian Conference on EurAsia-ICT 2002: Information and Communication Technology, LNCS 2510, (2002) October 585-865; Shiraz, Iran
[4] J.-S. Kim, E. Oh, H.-O. Lee, and Y.-N. Heo, Topological and communication aspects of hyper-star graphs. Proceedings of the 18th International Symposium on Computer and Information Sciences, LNCS 2869, (2003) November 51-58; Antlya, Turkey
[5] J.-S. Kim, E. Cheng, L. Liptak, and H.-O. Lee, Embedding hypercubes, rings and odd graphs into hyper-stars. International Journal of Computer Mathematics, Vol.86, No.5, pp.771-778 (2009)
[6] J.-S. Kim, E. Cheng, L. Liptak, and H.-O. Lee, A note on embeddings among folded hypercubes, even graphs and odd graphs. International Journal of Computer Mathematics, Vol.8, No.5, pp.882-891(2011)
[7] E. Cheng, P. Hu, R. Jia, and L. Lipt´ak, Matching preclusion and conditional matching preclusion for bipartite interconnection networks II: Cayley graphs generated by transposition trees and hyper-stars. Networks, Vol.59, No.4, pp.357-364 (2012)
[8] L. Lipt´ak, E. Cheng, J.-S. Kim, and S. W. Kim, One-to-many node-disjoint paths of hyper-star networks. Discrete Applied Mathematics, Vol.160, No.13–14, pp.2006-2014 (2012)
[9] A. Bossard, A set-to-set disjoint paths routing algorithm in hyper-star graphs, ISCA International Journal of Computers and Their Applications, Vol.21, No.1, pp.76-82 (2014)
[10] S. N. Bhatt, F. R. K. Chung, F. T. Leighton, and A. L. Rosenberg, Efficient embeddings of trees in hypercubes. SIAM Journal on Computing, Vol. 21, pp.151-162 (1992)
[11] A. K. Gupta, D. Nelson, and H. Wang, Efficient embeddings of ternary trees into hypercubes. Journal of Parallel and Distributed Computing, Vol.63, pp.619-629 (2003)
[12] V. Heun and E. W. Mayr, Efficient Dynamic Embeddings of Binary Trees into Hypercubes. Journal of Algorithms, Vol.43, pp.51-84 (2002)
[13] H.-S. Lim, J.-H. Park, and K.-Y. Chwa, Embedding trees in recursive circulants. Discrete Applied Mathematics, Vol.69, pp.83-99 (1996)